/* 8911106 302933981 Ofri Keidar */

/******************************************************************************
* Student Name: Ofri Keidar
* Exercise Name: Ex3
* File Description: Class Graph's implementation, including implementation of
* 					Edge-Linked-List and Edge-In-Graph classes
******************************************************************************/

#include "Graph.h"
#define NODE_DUMMY_INIT_VAL 0 // node list's head and tail dummy nodes are initialized with graph node data with this value

//////////////////////////////////////////////////////////////////////////////////// class EdgeInGraph's methods

//////////////////////////////////////////////////////////////////// public methods

/***************************************************************************************
* function name: EdgeInGraph(const Node& nodeOut, const Node& nodeIn)
* The Input: Two refernces to nodes to be linked by new edge
* The output: None
* The Function operation: Sets out-node and in-node references according to given origin
* 						  and destination, respectively. Given nodes are graph's nodes
* 						  (hence no need to copy nodes)
***************************************************************************************/
Graph::EdgeInGraph::EdgeInGraph(const Node& nodeOut, const Node& nodeIn): m_out(nodeOut), m_in(nodeIn) { }

/***************************************************************************************
* function name: EdgeInGraph(const EdgeInGraph& edgeToCopy)
* The Input: Edge to be copied
* The output: None
* The Function operation: Sets new edge's node-pointer attributes as given edge's
***************************************************************************************/
Graph::EdgeInGraph::EdgeInGraph(const EdgeInGraph& edgeToCopy): m_out(edgeToCopy.m_out), m_in(edgeToCopy.m_in) { }

/***************************************************************************************
* function name: ~EdgeInGraph()
* The Input: None
* The output: None
* The Function operation: Destructs edge
***************************************************************************************/
Graph::EdgeInGraph::~EdgeInGraph() { }

/***************************************************************************************
 * function name: == (const EdgeInGraph& other) const
 * The Input: Edge operand to compare with
 * The output: True if given operand is equal to object
 * The Function operation: Uses Node object's comparison operator and compares both edges'
 * 						   node attributes
 ***************************************************************************************/
bool Graph::EdgeInGraph::operator == (const EdgeInGraph& other) const {
	return (m_out == other.m_out) && (m_in == other.m_in);
}

/***************************************************************************************
 * function name: != (const EdgeInGraph& other) const
 * The Input: Edge operand to compare with
 * The output: True if given operand is not equal to object
 * The Function operation: Returns negation of "==" operator between edges
 ***************************************************************************************/
bool Graph::EdgeInGraph::operator != (const EdgeInGraph& other) const {
	return !(*this == other);
}

/***************************************************************************************
 * function name: < (const EdgeInGraph& other) const
 * The Input: Edge operand to compare with
 * The output: True if given operand's out and in nodes' values are bigger than object's
 * The Function operation: Uses Node object's comparison operator and compares both edges'
 * 						   node attributes
 ***************************************************************************************/
bool Graph::EdgeInGraph::operator < (const EdgeInGraph& other) const {
	return (m_out < other.m_out) && (m_in < other.m_in);
}

/***************************************************************************************
 * function name: <= (const EdgeInGraph& other) const
 * The Input: Edge operand to compare with
 * The output: True if both edges' out node value is equal and  given operand's in node
 * 			   value is bigger
 * The Function operation: Uses Node object's comparison operator and compares both edges'
 * 						   node attributes
 ***************************************************************************************/
bool Graph::EdgeInGraph::operator <= (const EdgeInGraph& other) const {
	return (m_out == other.m_out) && (m_in < other.m_in);
}

/***************************************************************************************
 * function name: toString() const
 * The Input: None
 * The output: The string: "(out_Node_Value->in_Node_Value)"
 * The Function operation: Converts edge to a string
 ***************************************************************************************/
 const string Graph::EdgeInGraph::toString() const {
	return "(" + m_out.toString() + "->" + m_in.toString() + ")"; // create and return output string
 }


/***************************************************************************************
* function name: << (ostream &os, const EdgeInGraph& edgeToPrint)
* The Input: Reference to Edge to be printed
* The output: ostream reference
* The Function operation: Converts edge's nodes to int and prints edge in format
* 					      "(OUT_NODE->IN_NODE)"
***************************************************************************************/
ostream& operator << (ostream &os, const Graph::EdgeInGraph& edgeToPrint) {
	return os << "(" << edgeToPrint.m_out.toInt() << "->" << edgeToPrint.m_in.toInt() << ")";
}

//////////////////////////////////////////////////////////////////////////////////// class EdgeLinkedList::ListNode's methods

//////////////////////////////////////////////////////////////////// public methods

/***************************************************************************************
* function name: ListNode(EdgeInGraph& const edgeToPoint)
* The Input: Edge data to be set as data attribute
* The output: None
* The Function operation: Initializes edge data reference to given edge.
*						  Previous and next list node pointers are initialized as NULL and
*						  index is initialized as INDEX_INIT_VAL because the new list node's
*						  position in the linked list is not set yet
***************************************************************************************/
Graph::EdgeLinkedList::ListNode::ListNode(EdgeInGraph& edgeData): m_edgeData(edgeData) {
	// new list node is not yet linked to the list
	m_prevListNode = NULL;
	m_nextListNode = NULL;
}

/****************************************************************************************
* function name: ~ListNode()
* The Input: None
* The output: None
* The Function operation: Deletes edge data (but not the nodes that the edge data links).
* 				          Next and previous list nodes are linked and the next list nodes'
* 					      indices are decremented
***************************************************************************************/
Graph::EdgeLinkedList::ListNode::~ListNode() {

	delete &m_edgeData; // // delete allocated memory for edge

	// link next node and previous node
	if (m_nextListNode != NULL) { // not end of list
		m_nextListNode->m_prevListNode = m_prevListNode;
	}
	if (m_prevListNode != NULL) { // not beginning of list
		m_prevListNode->m_nextListNode = m_nextListNode;
	}
}

//////////////////////////////////////////////////////////////////////////////////// class EdgeLinkedList's methods

//////////////////////////////////////////////////////////////////// private methods

/***************************************************************************************
* function name: findPlace(const EdgeInGraph& newEdge)
* The Input: Pointer to graph node to add
* The output: List node pointer to which the new graph node should be linked.
* 	          If a graph node with new graph node's number already exists, NULL is returned
* The Function operation: Uses 2 list node pointers- one to point at previous list node being
*			              scanned and another one to point at current node on list.
*	                      Method compares current graph node's number with given graph node's
*	                      number.
*			              If numbers are equal, given graph node cannot be added and NULL is
*			              returned. If current graph node's number is smaller than new graph
*			              node's, a pointer to current list node is returned
***************************************************************************************/
Graph::EdgeLinkedList::ListNode* Graph::EdgeLinkedList::findPlace(const EdgeInGraph& newEdge) const {

	ListNode* after = m_headDummy; // pointer to previous node being scanned
	ListNode* curr = after->m_nextListNode; // pointer to current node being scanned
	while (after->m_nextListNode != m_tailDummy) {

		if (newEdge == curr->m_edgeData ) {
			return NULL; //duplicate edge found
		}

		// sort mainly by out-node
		// if new edge's out-node is smaller than current edge's on list, link before it
		if ( newEdge.getNodeOut() < curr->m_edgeData.getNodeOut() ) {
			return curr;
		}

		// sort secondarily by in-node
		/* if new edge's out-node is equal to current edge's on list, link before it only if
		 * new edge's in-node is smaller than current edge's */
		if (newEdge <= curr->m_edgeData) {
			return curr;
		}

		// move to next node on list
		after = curr;
		curr = curr->m_nextListNode;
	} // while (after->m_nextListNode != m_tailDummy)
	return curr;
}

/***************************************************************************************
* function name: internalAdd(EdgeInGraph& edgeToAdd, Node* before)
* The Input: Reference to edge to be added and a pointer to the list node where the
* 			 new edge will be linked
* The output: None
* The Function operation: A new list node is created pointing to edge to be added.
*			              Method links the new list node before the given list node and
*			              then increments next list nodes' indices
***************************************************************************************/
void Graph::EdgeLinkedList::internalAdd(EdgeInGraph& edgeToAdd, ListNode* before) {

	ListNode* newListNode = new ListNode(edgeToAdd); // create a list node pointing to new edge
	// link list node to list
	ListNode* temp = before->m_prevListNode;
	newListNode->m_nextListNode = before;
	before->m_prevListNode = newListNode;

	newListNode->m_prevListNode = temp;
	temp->m_nextListNode = newListNode;
}

//////////////////////////////////////////////////////////////////// public methods

/***************************************************************************************
* function name: EdgeLinkedList()
* The Input: None
* The output: None
* The Function operation: List's head and tail are pointers to list nodes which do not point
*			              at edges (point NULL). This implementation prevents the
*			              need to check if previous/next list nodes are NULL- makes code
*		                  more quick because there are less conditions to check
***************************************************************************************/
Graph::EdgeLinkedList::EdgeLinkedList() {

	// create dummy list nodes at list's begging and end to avoid checking NULL values

	/* create graph nodes to be set as head and tail's edge data
       the dummy graph nodes and edges will be deleted in head and tail's destructors */
	Node& headDataDummyOut = *(new Node(NODE_DUMMY_INIT_VAL)); // create dummy out-node
	Node& headDataDummyIn = *(new Node(NODE_DUMMY_INIT_VAL)); // create dummy in-node
	EdgeInGraph& headEdgeDummy = *(new EdgeInGraph(headDataDummyOut, headDataDummyIn)); // create dummy edge

	Node& tailDataDummyOut = *(new Node(NODE_DUMMY_INIT_VAL)); // create dummy out-node
	Node& tailDataDummyIn = *(new Node(NODE_DUMMY_INIT_VAL)); // create dummy in-node
	EdgeInGraph& tailEdgeDummy = *(new EdgeInGraph(tailDataDummyOut, tailDataDummyIn)); // create dummy edge

	// set dummy graph nodes as head and tail's data
	m_headDummy = new ListNode(headEdgeDummy);
	m_tailDummy = new ListNode(tailEdgeDummy);

	// link list's head and tail
	m_headDummy->m_nextListNode = m_tailDummy;
	m_tailDummy->m_prevListNode = m_headDummy;
	m_currNode = m_headDummy; // initialize current node pointer
}

/***************************************************************************************
 * function name: ~EdgeLinkedList()
 * The Input: None
 * The output: None
 * The Function operation: Scans list from start to end and deletes each node
 ***************************************************************************************/
Graph::EdgeLinkedList::~EdgeLinkedList() {

 	// scan list and delete list nodes
 	ListNode* currNode = m_headDummy;
 	ListNode* prevNode = m_headDummy;

 	while (currNode != NULL) {
 		// move to next node on list and delete the previous which has been scanned
 		currNode = currNode->m_nextListNode;
 		delete prevNode;
 		prevNode = currNode;
 	}
 	delete prevNode; // delete last node on list
}

/***************************************************************************************
* function name: addNode(const EdgeInGraph& newEdge)
* The Input: Reference to edge to be added
* The output: True if graph was added, False is not
* The Function operation: Method calls findPlace to find where the new edge should
*			              be added. If no such place was found (returned value is NULL)
*		                  the method returns False. Otherwise, it calls internalAdd to
*			              add the new edge to the list and returns True
***************************************************************************************/
bool Graph::EdgeLinkedList::addNode(const EdgeInGraph& newEdge) {

	ListNode* before = findPlace(newEdge); // find where, if any, edge can be added

	// check if duplicate id was found
	if (before == NULL) {
		return false;
	}

	EdgeInGraph* edgeToAdd = new EdgeInGraph(newEdge); // copy given edge and add copy to edge list
	internalAdd(*edgeToAdd, before); // add edge
	return true;
}

/***************************************************************************************
 * function name: removeListNode(const EdgeInGraph& edgeDataToRmv)
 * The Input: Reference to edge data whose list node should be removed
 * The output: True if removal was successful, False if not
 * The Function operation: Scans list and compares each list node's edge data with given
 * 						   value. If a match is found, current list node and edge data
 * 						   are deleted and True is returned. Otherwise, list is not changed
 * 						   and False is returned
 ***************************************************************************************/
bool Graph::EdgeLinkedList::removeListNode(const EdgeInGraph& edgeDataToRmv) {

	ListNode* currListNode = m_headDummy->m_nextListNode; // point to first list node
	// scan list and search for a list node that holds given data
	while (currListNode != NULL) {
		if (currListNode->m_edgeData == edgeDataToRmv) { // match found, remove current list node
			delete currListNode;
			return true;
		}
		currListNode = currListNode->m_nextListNode; // match not found, move to next node
	}
	return false; // if reached here match was not found
}

/***************************************************************************************
 * function name: <<
 * The Input: Reference to edge liked list to be printed
 * The output: ostream reference
 * The Function operation: Scans list and prints nodes, using Node object's ostream
 * 			               operator. Braces are also printed
 ***************************************************************************************/
ostream& operator << (ostream &os, const Graph::EdgeLinkedList& listToPrint) {
	// scan list and print each node
	Graph::EdgeLinkedList::ListNode* currListNode = listToPrint.m_headDummy->m_nextListNode; // point to first node on list

	if (currListNode == listToPrint.m_tailDummy) { // list is empty, done printing
		return os << "";
	}

	// if reached here, list is not empty
	cout << currListNode->m_edgeData; // print first edge
	currListNode = currListNode->m_nextListNode; // move to next edge

	while (currListNode != listToPrint.m_tailDummy) { // scan list to its end
		cout << "," << currListNode->m_edgeData; // print current edge
		currListNode = currListNode->m_nextListNode; // move to next node on list
	}
	// done printing the list
	return os << "";
}

/***************************************************************************************
 * function name: searchByKey(const EdgeInGraph& key)
 * The Input: Edge (in graph) to look for
 * The output: Pointer to edge that's equal to given key. If no such edge exists,
 * 			   NULL is returned.
 * The Function operation: Scans list- if a match is found, a pointer to this edge is
 * 						   returned. If not, NULL is returned.
 * 						   Method does not change list object
 ***************************************************************************************/
const Graph::EdgeInGraph* Graph::EdgeLinkedList::searchByKey(const EdgeInGraph& key) const {

	ListNode* currListNode = m_headDummy->m_nextListNode; // pointer to first list node in list

	// scan graph's node list to its end
	while (currListNode != m_tailDummy) {

		// check if current graph node on list is equal to given key
		if (currListNode->m_edgeData == key) {
			// if they are equal, return pointer to current edge
			return &(currListNode->m_edgeData);
		}
		// move to next node
		currListNode = currListNode->m_nextListNode;
	} // while (currListNode != m_tailDummy)
	// if reached here, key was not found- return NULL
	return NULL;
}

/***************************************************************************************
 * function name: searchByKey(const Node& outNode, const Node inNode)
 * The Input: Out and in nodes of edge to look for
 * The output: Pointer to edge whose out and in node are equal to given keys. If no such
 * 			   edge exists, NULL is returned.
 * The Function operation: Scans list- if a match is found, a pointer to this edge is
 * 						   returned. If not, NULL is returned.
 * 						   Method does not change list object
 ***************************************************************************************/
const Graph::EdgeInGraph* Graph::EdgeLinkedList::searchByKey(const Node& outNode, const Node inNode) const {

	ListNode* currListNode = m_headDummy->m_nextListNode; // pointer to first list node in list

	// scan graph's node list to its end
	while (currListNode != m_tailDummy) {

		// check if current graph node on list is equal to given key
		if (currListNode->m_edgeData.getNodeOut() == outNode && currListNode->m_edgeData.getNodeIn() == inNode) {
			// if they are equal, return pointer to current edge
			return &(currListNode->m_edgeData);
		}

		// move to next node
		currListNode = currListNode->m_nextListNode;

	} // while (currListNode != m_tailDummy)
	// if reached here, key was not found- return NULL
	return NULL;
}

/***************************************************************************************
 * function name: removeEdges(const Node& nodeToRmv)
 * The Input: Reference to graph node that edges that link it should be removed
 * The output: None
 * The Function operation: Removes all edges that have given graph node as out/in node
 ***************************************************************************************/
void Graph::EdgeLinkedList::removeEdges(const Node& nodeToRmv) {
	ListNode* currListNode = m_headDummy->m_nextListNode; // pointer to first list node in list
	// scan graph's node list to its end
	while (currListNode != m_tailDummy) {
		if (currListNode->m_edgeData.getNodeOut() == nodeToRmv || currListNode->m_edgeData.getNodeIn() == nodeToRmv) {
			delete currListNode; // match found, delete list node
		}
		currListNode = currListNode->m_nextListNode; // move to next node on list
	}
}

/***************************************************************************************
 * function name: incrmntCurrNode()
 * The Input: None
 * The output: False if reached list's tail dummy node or if a next list node does
 * 			   not exist. Otherwise, returns true
 * The Function operation: Sets current node pointer to point at its next node.
 * 					       If the next node is NULL or list's dummy node, current node
 * 					       is not incremented and False is returned.
 * 					       Otherwise, current node pointer is incremented and True returned
 ***************************************************************************************/
bool Graph::EdgeLinkedList::incrmntCurrNode() {

	if (m_currNode->m_nextListNode == m_tailDummy) { // reached list's end
		return false;
	}

	m_currNode = m_currNode->m_nextListNode; // has not reached end yet, move to next node
	return true;
}

/***************************************************************************************
 * function name: operator == (const EdgeLinkedList& listOperand)
 * The Input: Edge linked list to compare with
 * The output: True if all edges are equal, False if not
 * The Function operation: Compares each list's nodes. Method does not change the object
 ***************************************************************************************/
bool Graph::EdgeLinkedList::operator == (const EdgeLinkedList& listOperand) const {
	// scan both list and compare nodes
	ListNode* currOnObject = m_headDummy->m_nextListNode; // point to object's start
	ListNode* currOnOperand = listOperand.m_headDummy->m_nextListNode; // point to operand's start

	// scan until one of list's end is reached
	while (currOnObject != m_tailDummy && currOnOperand != listOperand.m_tailDummy) {
		if (currOnObject->m_edgeData != currOnOperand->m_edgeData) {
			return false; // mismatch found, return False
		}
		// move to next node on both lists
		currOnObject = currOnObject->m_nextListNode;
		currOnOperand = currOnOperand->m_nextListNode;
	}

	// done scanning and did not find mismatch, lists are equal only if both of them reached their end
	return currOnObject == m_tailDummy && currOnOperand == listOperand.m_tailDummy;
}

//////////////////////////////////////////////////////////////////////////////////// class Graph

//////////////////////////////////////////////////////////////////// private methods

/***************************************************************************************
 * function name: CopyNewEdges(const Graph& sourceGraph)
 * The Input: Reference to graph that its edges should be copied
 * The output: None
 * The Function operation: Scans given graph's edge list and adds to object a copy of each
 * 						   edge that does not appear in object. Replaces the use of edge
 * 						   list's copy constructor because and Edge-Linked-List object
 * 						   cannot access graph's nodes, but edges should have references
 * 						   to graph object's nodes and not the graph being copied's nodes
 ***************************************************************************************/
void Graph::CopyNewEdges(const Graph& sourceGraph) {

	sourceGraph.m_edgeList->initializeCurrNode(); // initialize current node pointer on given graph's edge list
	bool keepScanning = sourceGraph.m_edgeList->incrmntCurrNode(); // flag to indicate if reached given graph's edge list's end
	const EdgeInGraph* isEdgeInGraph; // used to indicate if current edge on given graph's edge list appears in result graph
	while (keepScanning) {
		isEdgeInGraph = m_edgeList->searchByKey(sourceGraph.m_edgeList->getCurrEdge());
		if (isEdgeInGraph == NULL) { // edge should be added to result graph
			// get result graph's copies of current edge's nodes
			const Node& outNode = *m_nodeList->searchByKey(sourceGraph.m_edgeList->getCurrEdge().getNodeOut()); // reference to out node
			const Node& inNode = *m_nodeList->searchByKey(sourceGraph.m_edgeList->getCurrEdge().getNodeIn()); // reference to in node
			EdgeInGraph& newEdge = *(new EdgeInGraph(outNode, inNode)); // create an edge linking these nodes
			m_edgeList->addNode(newEdge); // add new edge to new graph
		}
		keepScanning = sourceGraph.m_edgeList->incrmntCurrNode(); // move to next edge on given graph's edge list
	}
	sourceGraph.m_edgeList->initializeCurrNode(); // done scanning, initialize current node pointer on given graph's edge list
	return;
}

//////////////////////////////////////////////////////////////////// public methods

/***************************************************************************************
* function name: Graph()
* The Input: None
* The output: None
* The Function operation: Allocates an empty node linked list and an empty edge linked list
***************************************************************************************/
Graph::Graph() {
	m_nodeList = new NodeLinkedList(); // allocate a new node list
	m_edgeList = new EdgeLinkedList(); // allocate a new edge list
}

/***************************************************************************************
* function name: Graph(const Graph& graphToCopy)
* The Input: Graph to be copied
* The output: None
* The Function operation: Copies given graph's node and edge lists and assigns new graph's
* 						  list pointers to the copies
***************************************************************************************/
Graph::Graph(const Graph& graphToCopy) {
	m_nodeList = new NodeLinkedList(*graphToCopy.m_nodeList); // copy given graph's node list
	m_edgeList = new EdgeLinkedList(); // allocate a new edge list
	/* copy given graph's edge list and add edges to new graph.
	   the new graph's edges will link new graph's nodes */
	CopyNewEdges(graphToCopy);
}

/***************************************************************************************
* function name: ~Graph()
* The Input: None
* The output: None
* The Function operation: Deletes node and edge lists. Edge list is deleted first,
* 					      otherwise edge list's node will hold invalid data
***************************************************************************************/
Graph::~Graph() {
	// delete allocated data
	delete m_edgeList;
	delete m_nodeList;
}

/***************************************************************************************
 * function name: << (ostream &os, const Graph& graphToPrint)
 * The Input: Reference to Graph to be printed
 * The output: ostream reference
 * The Function operation: Uses node and edge lists ostream operators in order to print
 * 					       the lists
 ***************************************************************************************/
ostream& operator << (ostream &os, const Graph& graphToPrint) {
	cout << "|";
	cout << *graphToPrint.m_nodeList; // print graph's node list
	cout << "|";
	cout << *graphToPrint.m_edgeList; // print graph's edge list
	cout << "|";
	// return an empty string because list's printing operators perform printing task
	return os << "";
}

/***************************************************************************************
 * function name: operator >> (istream &is, Graph& graphToSet)
 * The Input: Reference to istream object and reference to graph to be set
 * The output: istream reference
 * The Function operation: Deletes given graph's edge and node list. Then reads input.
 * 						   If No nodes were given, graph will be set as empty graph.
 * 						   Otherwise, node list is extracted from input and each read node
 * 						   is added to the graph. Then edge list is extracted from input
 * 						   and given edges are added with references to graph's nodes
 ***************************************************************************************/
istream& operator >> (istream &is, Graph& graphToSet) {

	delete graphToSet.m_edgeList; // delete given graph's edge list
	delete graphToSet.m_nodeList; // delete given graph's node list
	// allocate empty lists for given graph's attributes
	graphToSet.m_nodeList = new NodeLinkedList();
	graphToSet.m_edgeList = new Graph::EdgeLinkedList();

	// read node list from input
	char c; // used to read non-numeric data
	int firstNumericData; // used to read numeric data
	int secondNumericData; // also used to read numeric data

	// read node list
	cin >> c; // get "|" to begin node list
	cin >> c; // get next character

	if (c == '|') { // no nodes given, given graph will be an empty graph
		// read all "||" left to allow correct input reading for the rest of the program
		cin >> c;
		cin >> c;
		return is;
	}

	if (c == '-') { // first number is negative
		cin >> firstNumericData; // read as a number
		firstNumericData = -firstNumericData; // change sign to negative
		Node& newNode = *(new Node(firstNumericData)); // create a node holding current value
		graphToSet.m_nodeList->addNode(newNode); // add new node to graph
		cin >> c; // get next character

		while (c != '|') { // read the rest of the nodes
			cin >> firstNumericData; // get node number
			Node& newNode = *(new Node(firstNumericData)); // create a node holding current value
			graphToSet.m_nodeList->addNode(newNode); // add new node to graph
			cin >> c; // get "," or "|"
		}

	} else if (isdigit(c)) { // read a digit
		/* get current node's first digit,
		 * use ASCII to extract numerical value of character representing the digit */
		firstNumericData = c-'0';
		// read all digits from right to left
		cin >> c; // get next character
		while (isdigit(c)) { // keep reading digits
			firstNumericData *= 10; // found more digits at the left
			firstNumericData += c-'0'; // add digit
			cin >> c; // get next character
		}

		Node& newNode = *(new Node(firstNumericData)); // create a node holding current value
		graphToSet.m_nodeList->addNode(newNode); // add new node to graph
		// now input can be ", NODE_VALUE" or "|", read the rest of the nodes
		while (c != '|') { // read the rest of the nodes
			cin >> firstNumericData; // get node number
			Node& newNode = *(new Node(firstNumericData)); // create a node holding current value
			graphToSet.m_nodeList->addNode(newNode); // add new node to graph
			cin >> c; // get "," or "|"
		}
	} // else if ('0' <= c && c <= '9')

	// read edge list to its end
	do {
		cin >> c; // get "(" or '|'
		if (c == '|') { // if edge list's read character is '|', no edges were given
			return is;
		}

		cin >> firstNumericData; // get current edge's out node
		cin >> c; // get "-"
		cin >> c; // get ">"
		cin >> secondNumericData; // get current edge's in node
		// get references to out and in nodes in graph
		const Node& outNode = *graphToSet.m_nodeList->searchByKey(firstNumericData); // get out node
		const Node& inNode = *graphToSet.m_nodeList->searchByKey(secondNumericData); // get in node
		// create an edge linking these nodes and add it to graph
		const Graph::EdgeInGraph& newEdge = Graph::EdgeInGraph(outNode, inNode);
		graphToSet.m_edgeList->addNode(newEdge);
		cin >> c; // get ")"
		cin >> c; // get "," or "|"
	} while (c != '|');
	return is; // done reading string
}

/***************************************************************************************
 * function name: operator + (const Node& nodeOperand)
 * The Input: Reference to node operand
 * The output: Result graph of adding operation
 * The Function operation: Graph object is copied. Method uses "+=" operand between graph
 * 					       and node to add given node to graph's copy, copy is returned
 ***************************************************************************************/
const Graph Graph::operator+(const Node& nodeOperand) const {
	Graph resultGraph = Graph(*this); // copy graph object
	resultGraph += nodeOperand; // add node to graph's copy
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator + (const EdgeInGraph& edgeOperand)
 * The Input: Reference to node operand
 * The output: Result graph of adding operation
 * The Function operation: Graph object is copied. Method uses "+=" operand between graph
 * 					       and edge to add given edge to graph's copy, copy is returned
 ***************************************************************************************/
const Graph Graph::operator+(const Edge& edgeOperand) const {
	Graph resultGraph = Graph(*this); // copy graph object
	resultGraph += edgeOperand; // add node to graph's copy
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator + (const Graph& graphOperand)
 * The Input: Reference to graph operand
 * The output: Result graph of adding operation
 * The Function operation: Graph object is copied. Method uses "+=" operand between graphs
 * 					       to add given graph to graph's copy, copy is returned
 ***************************************************************************************/
const Graph Graph::operator+(const Graph& graphOperand) const {
	Graph resultGraph = Graph(*this); // copy graph object
	resultGraph += graphOperand; // add given graph to object's copy
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator - (const Node& nodeOperand)
 * The Input: Reference to graph node operand
 * The output: Result graph of operation
 * The Function operation: Copies graph object. If given node appears in copy's edge list,
 * 					       all edges that have this node as out/in node are removed from
 * 						   graph's copy. Then node is removed from copy's list and copy
 * 						   is returned
 ***************************************************************************************/
const Graph Graph::operator-(const Node& nodeOpearand) const {
	Graph resultGraph = (*this); // copy graph
	resultGraph -= nodeOpearand; // remove given edge from graph's copy
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator - (const Edge& edgeOperand)
 * The Input: Reference to edge operand
 * The output: Result graph of operation
 * The Function operation: Copies graph object. If given edge appears in copy's edge list,
 * 						   edge is removed from copy's list (nodes are not changed)
 * 						   and copy is returned
 ***************************************************************************************/
const Graph Graph::operator-(const Edge& edgeOpearand) const {
	Graph resultGraph = (*this); // copy graph
	resultGraph -= edgeOpearand; // remove given edge from graph's copy
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator - (const Graph& graphOperand)
 * The Input: Reference to graph operand
 * The output: Result graph of operation
 * The Function operation: Copies operator's activating graph object. Given graph's edge
 * 					       list is scanned and edges that do appear in activating
 * 					       graph's edge list are removed from graph's copy. Same procedure
 * 					       for nodes. Copy is returned.
 ***************************************************************************************/
const Graph Graph::operator-(const Graph& graphOperand) const {
	Graph resultGraph = Graph(*this); // copy graph object
	resultGraph -= graphOperand; // remove given graph from object's copy
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator = (const Graph& graphOperand)
 * The Input: Reference to new graph's value
 * The output: Reference to graph object after assignment
 * The Function operation: If given graph is the activating object, reference to the object
 * 				           is returned. Otherwise, graph's node and edge lists are deleted
 * 				           and given graph's lists are set as new graph's attributes
 ***************************************************************************************/
Graph& Graph::operator=(const Graph& graphOperand) {

	// check if given graph is the object
	if (this == &graphOperand) {
		return *this; // return activating object
	}

	// if reached here, given graph is not the object
	// delete ojbect's attributes
	delete m_edgeList;
	delete m_nodeList;

	m_nodeList = new NodeLinkedList(*graphOperand.m_nodeList); // copy given graph's node list
	m_edgeList = new EdgeLinkedList(); // allocate a new edge list

	/* copy given graph's edge list and add edges to new graph.
	   the new graph's edges will link new graph's nodes */
	CopyNewEdges(graphOperand);
	return *this; // return activating object after assignment
}

/***************************************************************************************
 * function name: operator += (const Node& nodeOperand)
 * The Input: Reference to node operand
 * The output: Result graph of adding operation
 * The Function operation: If given node appears in graph, graph is returned. Otherwise
 * 						   given node is added and then graph is returned
 ***************************************************************************************/
Graph& Graph::operator+=(const Node& nodeOperand) {

	// check if given node appears in graph
	const Node* nodeInGraph = m_nodeList->searchByKey(nodeOperand);
	if( nodeInGraph != NULL) { // if node is in graph, return the graph object unchanged
		return *this;
	}
	// if reached here, node does not appear in graph
	m_nodeList->addNode(nodeOperand); // add node to graph
	return *this; // return result
}

/***************************************************************************************
 * function name: operator += (const Edge& nodeOperand)
 * The Input: Reference to edge operand
 * The output: Result graph of adding operation
 * The Function operation: If given edge's nodes do not appear in graph, they are added.
 * 						   If given edge does not appear in graph, it is added.
 * 						   The graph is returned
 ***************************************************************************************/
Graph& Graph::operator+=(const Edge& edgeOpearand) {

	// if given edge's nodes do not appear in graph, add them
	*this += edgeOpearand.getNodeOut();
	*this += edgeOpearand.getNodeIn();

	// get reference to copy of given edge's nodes in graph's copy
	const Node& outNode = *m_nodeList->searchByKey(edgeOpearand.getNodeOut()); // reference to out node
	const Node& inNode = *m_nodeList->searchByKey(edgeOpearand.getNodeIn()); // reference to in node

	// create a local edge-in-graph equal to edge operand- now can search for edge (argument type matches)
	const EdgeInGraph& edgeOperandCopy = EdgeInGraph(outNode, inNode);

	// if edge does not appear in graph, copy it and add copy to graph's copy
	if (m_edgeList->searchByKey(edgeOperandCopy) == NULL) {
		// create an edge linking nodes (from graph's list) with the same values of given edge's nodes
		EdgeInGraph& newEdge = *(new EdgeInGraph(outNode, inNode));
		m_edgeList->addNode(newEdge); // add new edge to graph's copy
	}
	return *this; // return result
}

/***************************************************************************************
 * function name: operator += (const Graph& graphOperand)
 * The Input: Reference to graph operand
 * The output: Result graph of adding operation
 * The Function operation: Uses "+=" operand between graph and node to add each node that
 * 						   appears in given graph but not in object. Then given graph's
 * 						   edge list is scanned and edges that do not appear in object
 * 						   are added (new edges will link objects nodes). Object is returned
 ***************************************************************************************/
Graph& Graph::operator+=(const Graph& graphOperand) {

	// scan given graph's node list and add each node that does not appear in graph object
	graphOperand.m_nodeList->initializeCurrNode(); // initialize current node pointer on given graph's node list
	bool keepScanning = graphOperand.m_nodeList->incrmntCurrNode(); // flag to indicate if reached given graph's node list's end
	while (keepScanning == true) {
		*this += graphOperand.m_nodeList->getCurrGraphNode();
		keepScanning = graphOperand.m_nodeList->incrmntCurrNode(); // move to next node on given graph
	}
	graphOperand.m_nodeList->initializeCurrNode(); // done scanning, initialize current node pointer on given graph's node list

	/* copy given graph's edge list and add edges to new graph.
	   the new graph's edges will link new graph's nodes */
	CopyNewEdges(graphOperand);
	return *this; // return result
}

/***************************************************************************************
 * function name: operator -= (const Node& nodeOperand)
 * The Input: Reference to graph node operand
 * The output: Result graph of operation
 * The Function operation: Uses "-" operator between graph and graph node to remove given
 * 						   graph node from object and returns the object after removal
 ***************************************************************************************/
Graph& Graph::operator-=(const Node& nodeOpearand) {
	// remove from graph's copy all edges that have this node as out/in node
	m_edgeList->removeEdges(nodeOpearand);
	// remove from graph's copy given node
	m_nodeList->removeListNode(nodeOpearand);
	return *this; // return result
}

/***************************************************************************************
 * function name: operator -= (const Edge& edgeOperand)
 * The Input: Reference to edge operand
 * The output: Result graph of operation
 * The Function operation: Uses "-" operator between graph and edge to remove given edge
 * 						   to object and returns the object after removal
 ***************************************************************************************/
Graph& Graph::operator-=(const Edge& edgeOpearand) {
	// create a local edge-in-graph equal to edge operand- now can search for edge (argument type matches)
	const EdgeInGraph& edgeOperandCopy = EdgeInGraph(edgeOpearand.getNodeOut(), edgeOpearand.getNodeIn());
	const EdgeInGraph* isInGraph = m_edgeList->searchByKey(edgeOperandCopy); // check if given edge appears in graph
	if (isInGraph != NULL) { // edge appears, remove it from graph's copy
		m_edgeList->removeListNode(edgeOperandCopy);
	}
	return *this;
}

/***************************************************************************************
 * function name: operator -= (const Graph& graphOperand)
 * The Input: Reference to graph operand
 * The output: Result graph of operation
 * The Function operation: Uses "-" operator between graphs to remove given graph's edges
 * 						   from object and returns the object after removal
 ***************************************************************************************/
Graph& Graph::operator-=(const Graph& graphOperand) {

	graphOperand.m_edgeList->initializeCurrNode(); // initialize given graph's current node pointer on edge list
	bool keepScanning = graphOperand.m_edgeList->incrmntCurrNode(); // flag to indicate if reached given graph's edge list's end

	// remove given graph's edges from graph's copy
	while (keepScanning == true) { // scan given graph's edge list to its end
		// remove given graph's current edge from graph's copy
		m_edgeList->removeListNode(graphOperand.m_edgeList->getCurrEdge());
		keepScanning = graphOperand.m_edgeList->incrmntCurrNode(); // move to next edge on given graph
	}
	graphOperand.m_edgeList->initializeCurrNode(); // done scanning, initialize given graph's current node pointer on edge list
	return *this; // return result
}

/***************************************************************************************
 * function name: operator ++ ()
 * The Input: None
 * The output: The graph object after its nodes' values were incremented
 * The Function operation: Scans nodes list and increments each node's value using
 * 						   node list's incrementNodesValue() method
 ***************************************************************************************/
Graph& Graph::operator++() {
	m_nodeList->incrementNodesValue(); // increment nodes' values
	return *this; // return graph after incrementing
}

/***************************************************************************************
 * function name: operator ++ (int)
 * The Input: None (the int in method's declaration is a dummy argument to differ from perfix)
 * The output: The graph object before its nodes' values were incremented
 * The Function operation: Copies the graph, increments its nodes' values and returns copy
 * 						   before incrementing
 ***************************************************************************************/
const Graph Graph::operator++(int) {
	Graph backupGraph = Graph(*this); // copy graph object
	++(*this); // increment graph object
	return backupGraph; // return the graph before it was incremented
}

/***************************************************************************************
 * function name: operator -- ()
 * The Input: None
 * The output: Reference to the graph object after its nodes' values were decremented
 * The Function operation: Scans nodes list and decrements each node's value using
 * 						   node list's incrementNodesValue() method
 ***************************************************************************************/
Graph& Graph::operator--() {
	m_nodeList->decrementNodesValue(); // decrement nodes' values
	return *this; // return graph after decrementing
}

/***************************************************************************************
 * function name: operator -- (int)
 * The Input: None (the int in method's declaration is a dummy argument to differ from perfix)
 * The output: The graph object before its nodes' values were decremented
 * The Function operation: Copies the graph, decrements its nodes' values and returns copy
 * 						   before decrementing
 ***************************************************************************************/
const Graph Graph::operator--(int) {
	Graph backupGraph = Graph(*this); // copy graph object
	--(*this); // increment graph object
	return backupGraph; // return the graph before it was incremented
}

/***************************************************************************************
 * function name: operator == (const Graph& graphOperand)
 * The Input: Graph operand to compare with
 * The output: True if graphs are equal, False if not
 * The Function operation: Uses node and edge list's "==" operator to check if lists
 * 						   are equal. True is returned only if both lists are equal
 ***************************************************************************************/
bool Graph::operator == (const Graph& graphOperand) const {
	// compare graphs' lists
	return *m_nodeList == *graphOperand.m_nodeList && *m_edgeList == *graphOperand.m_edgeList;
}

/***************************************************************************************
 * function name: operator != (const Graph& graphOperand)
 * The Input: Graph operand to compare with
 * The output: True if graphs are not equal, False if they are equal
 * The Function operation: Returns negation of "==" operator between graphs
 ***************************************************************************************/
bool Graph::operator != (const Graph& graphOperand) const {
	return !(*this == graphOperand);
}

/***************************************************************************************
 * function name: operator && (const Graph& graphOperand)
 * The Input: Reference to graph operand
 * The output: Graph with nodes and edges that are common to both operands
 * The Function operation: Scans object's node list. If current node being scanned appears
 * 					       in given graph, add it to result graph.
 * 					       Same procedure for edge list
 ***************************************************************************************/
const Graph Graph::operator && (const Graph& graphOperand) const {

	Graph resultGraph; // create an empty graph

	// scan object's node list and check if current node being scanned appears in result graph
	m_nodeList->initializeCurrNode(); // initialize current node pointer on object's node list
	bool keepScanning = m_nodeList->incrmntCurrNode(); // used to indicate if reached node list's end
	const Node* isNodeInGraph; // used to indicate if current node being scanned appears in given graph

	while (keepScanning == true) { // scan list to its end
		isNodeInGraph = graphOperand.m_nodeList->searchByKey(m_nodeList->getCurrGraphNode());
		if (isNodeInGraph != NULL) { // check if current node appears in given graph
			// node appears, add it to result graph
			resultGraph.m_nodeList->addNode(*isNodeInGraph);
		}
		keepScanning = m_nodeList->incrmntCurrNode(); // move to next list node on object's node list
	}
	m_nodeList->initializeCurrNode(); // done scanning, initialize current node pointer on object's node list

	// scan object's edge list and check if current edge being scanned appears in result graph
	m_edgeList->initializeCurrNode(); // initialize current node pointer on object's edge list
	keepScanning = m_edgeList->incrmntCurrNode(); // used to indicate if reached edge list's end
	const EdgeInGraph* isEdgeInGraph; // used to indicate if current edge being scanned appears in given graph

	while (keepScanning == true) { // scan list to its end
		isEdgeInGraph = graphOperand.m_edgeList->searchByKey(m_edgeList->getCurrEdge());
		if (isEdgeInGraph != NULL) { // check if current edge appears in given graph
			// edge appears, add it to result graph:
			// get reference to copy of given edge's nodes in result graph
			const Node& outNode = *resultGraph.m_nodeList->searchByKey(isEdgeInGraph->getNodeOut()); // reference to out node
			const Node& inNode = *resultGraph.m_nodeList->searchByKey(isEdgeInGraph->getNodeIn()); // reference to in node
			const EdgeInGraph& newEdge = EdgeInGraph(outNode, inNode);
			resultGraph.m_edgeList->addNode(newEdge); // add new edge to result graph
		}
		keepScanning = m_edgeList->incrmntCurrNode(); // move to next list node on object's node list
	}
	m_edgeList->initializeCurrNode(); // done scanning, initialize current node pointer on object's edge list
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator - () const
 * The Input: None
 * The output: Completing graph of object
 * The Function operation: Creates an empty graph and copies object's node list to the
 * 						   new graph. Then scans node list and for each node creates all
 * 						   possible edges. Before current edge is created, method checks
 * 						   if it appears in object's edge list. If it does not appear, it
 * 						   is created and added to new graph's edge list. Otherwise nothing
 * 						   is done. The new graph is returned
 ***************************************************************************************/
const Graph Graph::operator - () const {

	Graph resultGraph; // create an empty graph
	// copy object's node list to result graph
	delete resultGraph.m_nodeList;
	resultGraph.m_nodeList = new NodeLinkedList(*m_nodeList);

	// scan result graph's node list and for each node add edges that do not appear in object's edge list

	resultGraph.m_nodeList->initializeCurrNode(); // initialize current node pointer in result graph's node list
	m_nodeList->initializeCurrNode(); // initialize current node pointer in object's node list
	bool keepScanningResult = resultGraph.m_nodeList->incrmntCurrNode(); // indicate if reached result graph's node list's end
	bool keepScanningObject = m_nodeList->incrmntCurrNode(); // indicate if reached object's node list's end

	while (keepScanningResult == true) { // scan result graph's node list to its end

		const Node& currOutNode = resultGraph.m_nodeList->getCurrGraphNode(); // reference to current node on result graph

		// scan object's node list and find all possible edges
		while (keepScanningObject == true) { // scan object's list to its end

			// check if current node on object's list is different than current node on result graph's list
			if (currOutNode != m_nodeList->getCurrGraphNode() ) {
				// check if an edge linking current nodes exists in object's edge list
				const Node& currInNode = *resultGraph.m_nodeList->searchByKey(m_nodeList->getCurrGraphNode()); // reference to object's current node's copy on result graph
				if (m_edgeList->searchByKey(currOutNode, currInNode) == NULL) {
					// edge does not appear in object, add it to result graph
					EdgeInGraph& newEdge = *(new EdgeInGraph(currOutNode, currInNode)); // create a new edge linking current nodes on result graph
					resultGraph.m_edgeList->addNode(newEdge); // add new edge to result graph
				}
			} // if (currOutNode != m_nodeList->getCurrGraphNode() )

			keepScanningObject = m_nodeList->incrmntCurrNode(); // move to next node on object's node list
		} // while (keepScanningObject == true)

		m_nodeList->initializeCurrNode(); // initialize current node pointer in object's node list in order to scan again
		keepScanningObject = m_nodeList->incrmntCurrNode(); // move to next node on object's node list
		keepScanningResult = resultGraph.m_nodeList->incrmntCurrNode(); // move to next node on result graph's node list
	} // while (keepScanningResult == true)
	resultGraph.m_nodeList->initializeCurrNode(); // done scanning, initialize current node pointer in result graph's node list
	return resultGraph; // return result
}

/***************************************************************************************
 * function name: operator [] (const int& nodeValue) const
 * The Input:Node number
 * The output: String of all edges that have this node as an out node or an empty string
 * 			   if there is no node holding given number
 * The Function operation: Scans edge list and if current edge's out node's value
 * 				           holds given number, by using edge's toString() the string conversion
 * 				           of current edge is concatenated to result string
 ***************************************************************************************/
const string Graph::operator [] (const int& nodeValue) const {

	// check if there is a node holding given number
	if (m_nodeList->searchByKey(nodeValue) == NULL) {
		return ""; // if no node holds given number, return an empty string
	}

	// if reached here node exist
	string resultString = "["; // create a string to store result

	// find first relevant edge
	m_edgeList->initializeCurrNode(); // initialize current node pointer on edge list
	bool keepScanning = m_edgeList->incrmntCurrNode(); // indicate if reached edge list's end

	while (keepScanning == true) { // scan edge list to its end
		if ( nodeValue == m_edgeList->getCurrEdge().getNodeOut().toInt() ) { // check if current edge's out node hold given number
			resultString += m_edgeList->getCurrEdge().toString();
			break; // found first relevant edge
		}
		keepScanning = m_edgeList->incrmntCurrNode(); // move to next edge
	}

	// find the rest of the edges - scan edge list and check if current edge's out node hold given number
	keepScanning = m_edgeList->incrmntCurrNode(); // move to next edge
	while (keepScanning == true) { // continue scanning edge list to its end
		if ( nodeValue == m_edgeList->getCurrEdge().getNodeOut().toInt() ) { // check if current edge's out node hold given number
			resultString += "," + m_edgeList->getCurrEdge().toString();
		}
		keepScanning = m_edgeList->incrmntCurrNode(); // move to next edge
	}
	resultString += "]"; // add closing brace
	return resultString;
}
